﻿#include<ctime>
#include<iostream>
using namespace std;

struct Node
{
	int data;
	Node *pNext;
};

void PrintList(Node *pHead)
{
	if (pHead == NULL)
		return ;

	Node *p = pHead->pNext ;
	while ( p != NULL )
	{
		cout<<p->data<<"   ";
		p = p->pNext;
	}
	cout<<endl;
}

// adjust the pointer to quick sort linklist through two functions
Node *Partition(Node **ypBegin, Node *pEnd)
{
	Node *pPivot = *ypBegin;
	Node **ypLeftTail = ypBegin;
	Node **ypRightTail  = &(pPivot->pNext);

	Node *pWalk = pPivot->pNext;
	while (pWalk != pEnd)
	{
		if (pWalk->data < pPivot->data)
		{
			*ypLeftTail = pWalk;
			ypLeftTail = &(pWalk->pNext);
		}
		else
		{
			*ypRightTail = pWalk;
			ypRightTail = &(pWalk->pNext);
		}

		pWalk = pWalk->pNext;
	}

	*ypLeftTail = pPivot;
	*ypRightTail = pEnd;

	return pPivot;
}

void  QuickSort(Node **ypHead, Node *pEnd)
{
	if ( *ypHead != pEnd)
	{
		Node *pPivot = Partition(ypHead, pEnd);
		QuickSort(ypHead, pPivot);
		QuickSort(&(pPivot->pNext), pEnd);
	}
}

// through a function
void QuickSortForLinkList(Node **ypHead, Node *pEnd)
{
	if (*ypHead==pEnd || (*ypHead)->pNext==pEnd)
	{
		return;
	}

	Node *pPivot = *ypHead;
	Node **ypLeftTail = ypHead;
	Node **ypRightTail = &(pPivot->pNext);

	Node *pWalk = pPivot->pNext;
	while (pWalk != pEnd)
	{
		if (pWalk->data < pPivot->data)
		{
			*ypLeftTail = pWalk;
			ypLeftTail = &(pWalk->pNext);
		}
		else
		{
			*ypRightTail = pWalk;
			ypRightTail = &(pWalk->pNext);
		}

		pWalk = pWalk->pNext;
	}

	*ypLeftTail = pPivot;
	*ypRightTail = pEnd;

	QuickSortForLinkList(ypHead, pPivot);
	QuickSortForLinkList(&(pPivot->pNext), pEnd);
}

// Exchange the node data to quick sort Linklist through two functions
void Swap(int &p, int &q)
{
	if (p == q)
		return;

	q = p ^ q;
	p = p ^ q;
	q = p ^ q;
}

Node* Partition(Node* pBegin, Node* pEnd)
{
	int data = pBegin->data;
	Node* pLeft = pBegin;
	Node* pRight = pLeft->pNext;

	while (pRight != pEnd)
	{
		if (pRight->data < data)
		{
			pLeft = pLeft->pNext;
			Swap(pLeft->data, pRight->data);
		}

		pRight = pRight->pNext;
	}

	Swap(pLeft->data, pBegin->data);

	return pLeft;
}

void QuickSort(Node* pBeign, Node* pEnd)
{
	if(pBeign != pEnd)
	{
		Node* partion = Partition(pBeign,pEnd);
		QuickSort(pBeign,partion);
		QuickSort(partion->pNext, pEnd);
	}
}

void SelectionSort(Node *pHead)
{
	Node *pSortedNode;
	pSortedNode = pHead->pNext;
	while (pSortedNode != NULL)
	{
		Node *pTemp = pSortedNode;
		Node *pLoop=pSortedNode->pNext;
		while (pLoop != NULL)
		{
			if (pLoop->data < pTemp->data)
				pTemp =pLoop;
			pLoop = pLoop->pNext;
		}
		if (pTemp != pSortedNode)
		{
			int temp = pTemp->data;
			pTemp->data = pSortedNode->data;
			pSortedNode->data = temp;
		}
		pSortedNode = pSortedNode->pNext;
	}
}

Node *BuildList()
{
	Node *pHead = new Node;
	Node *pTail = pHead;

	srand((unsigned)time(NULL));
	for (int i=0; i<10; i++)
	{
		Node *pNode = new Node;
		pNode->data = rand()/100+1;
		
		pTail->pNext = pNode;
		pTail = pNode;
	}
	pTail->pNext = NULL;
	return pHead;
}

// Called function
void TestListQuick()
{
	Node *pHead = NULL;
	pHead = new Node;
	pHead->pNext = NULL;
	pHead ->data = 0;
	Node *p = NULL;

	srand((unsigned)time(NULL));
	for(int i=0; i<12; i++)
	{
		p = new Node;
		p->data = rand()/100 +1;
		p->pNext = pHead->pNext;
		pHead->pNext = p;
	}

	PrintList(pHead);

	cout<<"*********************************"<<endl;

	//QuickSort(pHead->pNext, NULL);
	QuickSort(&(pHead->pNext), NULL);
	//QuickSortForLinkList(&(pHead->pNext), NULL);

	PrintList(pHead);
}